O. G. Monakhov, E. A. Monakhova

Institute of Computational Mathematics and Mathematical Geophysics,

Siberian Division of Russian Academy of Sciences, Novosibirsk

The circulant networks and their various applications are the object of intensive investigations in computer science and discrete mathematics [1], [2], [3], [4], [7], [8], [9]. These graphs are realized as interconnection networks for some massively parallel processing systems (Intel Paragon, Cray T3D). In this work we consider a solution of problem of constructing optimal circulant network designs (the conversation to the well known (Degree/Diameter)-graph problem): Given the vertex number and the degree find a circulant with smallest diameter . Optimal graphs achieve the exact lower bounds for the diameter and, respectively, optimal features with respect to transmission delays, reliability and connectivity [1], [2] under implementation as interconnection networks in multimodule supercomputer systems.

There exists an analytical solution for synthesis of optimal circulants of degree 4 and any order [6], [1], [2]. In [1], [8], [4], [7] for loop circulant networks of degree 4 infinite families of values of , that are optimal for the diameter, or may be defined by analytical formulas, have been found. But under >4 this optimization problem is known as NP-hard. There exist [1], [3], some isolated analytical solutions, generating nearly optimal graphs. For some classes of loop circulant graphs are obtained ([3], the results of C. Delorme and C.Peyrat, indicated in [1]) with good approximation of diameter to its exact lower bound. For other analogous results [1] the diameters of graphs obtained are distinguished considerably from exact lower bounds.

We develop an original approach using genetic programming [5] to automatically generate analytical descriptions for families of (sub)optimal circulant networks.

A circulant graph , having the parametric description, is defined as follows.

Definition 1. Let nodes of graph are enumerated by numbers 0, 1, ...,-1 and let be a set of integers. The link between nodes and has a place, if and only if where is order of the graph, is its dimensionality, is the generator set.

The degree of a node in circulant graph =2. Graph when is known as a loop circulant network [1], [4], [3].

The diameter of is defined by where is the length of a shortest path from a node to a node . Let be an exact lower bound on the [1].

Definition 2. A graph is optimal if , and it is suboptimal if +1.

We will consider a solution of problem of finding analytical (described by formulas) descriptions for optimal circulants with the help of methods of genetic programming. It is necessary to find a set of functions , depending in a common case on and (or ) such, that given analytical description with generators , on a rather large range of gives optimal or nearly optimal graphs. It is known the exact description for =2 [6], [1], [2].

Theorem 1. For optimal two-dimensional circulant exists and has a description in the form , , where is the nearest integer to .

Under searching for a set of functions , a genetic programming algorithm (GPA) is used. The basic idea of the algorithm consists of evolutionary transformations over sets of analytical descriptions (formulas) based on natural selection: "strongest" survives, in this case giving the best result. The new applicants occur with the help of genetic operations, named mutation, crossover and, for variety of a population, operation of addition of new elements.

The genetic programming algorithm is based on simulation of the survival of the fittest in the population of individuals each of which presents a point in space of solutions of optimization graph problem. The individuals are presented by strings of functions (analytical representations of generator sets). Each population is a set of generator sets for given and taking in this range all values or some of them. The function named as fitness function evaluates the degree of approximation of a graph diameter to its exact lower bound on some range of changing . The purpose of GPA is to search for a minimum of .

The basic data in the program are sets of functions . The following method of data representation is used.

Under some assumption about a sufficient simplicity of desired functions, the set of operators was limited to such: on the set of variables and (or ) and natural constants {c}. The following template for each function is used:

where: - type of rounding, By an template function we create a expression for each function , with which already we can produce all evaluations and modifications. Thus, knowing concrete and , we can calculate a concrete value of . Sometimes, with an evaluation we can have mathematical errors, for example, evaluation of the root of a negative number or division by 0. In this situation fitness function (but only it requires an evaluation of a value ) returns a value indicating, that the given set of functions "is prohibited", and accordingly at the following iteration will be thrown out.

A formal description of the GPA, following [10], may be presented by 11-tuple:

where: - initial population; - space of individuals; N- population size; N- maximal length of individual; SEL: - selection operator; NEW: - new element operator; MUT: - mutation operator; [0,1] - mutation probability; CROS: - crossover operator; [0,1] - crossover probability; F:N - fitness function; N - termination criterion.

MUT: with probability [0,1] is applied to randomly chosen generators of the population . Mutation represents a modification of any individual, which number is selected accidentally. Modification is understood as a replacement of an operator (constant) into any other (randomly from the available list of operators and constants). In some cases there happens a deletion of elements (for example, mutation of an operator in a constant) and adding elements (mutation of a constant in an operator).

CROS: with probability [0,1] is applied to two generator sets from population . Crossover represents interchanging by the elements between two functions with probability [0,1] chosen from current population. That is we randomly select on one element in each function, and change them among themselves.

NEW: creation of the new element (individual) is generation of a random parameters for template functions. It allows to add an element of chance in creation of a population.

SEL: realizes the principle of the survival of the fittest: in population it selects the best individuals with minimal diameters (which describe the families of graphs).

Under searching for the optimum of fitness function F the iteration process in GPA is organized by the following way.

First iteration: it is a generation of the initial generation (population) . In the given moment it is carried out thus: with the help of operator NEW the all individuals of the population is created (with test and throw all "impractical" individuals). After filled out the whole array of generation, the best individuals are selected and saved in an array best.

One iteration: it is a step from a population towards the next :=SEL(MUT CROS)(). The basic step of the algorithm consists of creating new generation on the basis of array best with the help of mutation and crossover operations, and also adding some of the new individuals.

After an evaluation of fitness function for each individual of generation we make a comparison of a value of this function with values of fitness function of those individuals, which are saved in an array best. In the case if an element from a new generation is better than an element best [i], for some i, we put on a place i the new element, and all remaining ones we shift per unit of downwards. Thus, the best element is at the top of an array best.

Last iteration (termination criterion): the iterations are finished (1) after a given number of steps T=t or (2) after finding a given number of (sub)optimal graphs in given range of values of N.

By producing given number of basic steps of the algorithm, we obtain a set , which, in an association from parameters given with start, with this or that exactitude, describes the optimum or nearly optimum circulant graph.

The basic computing load is necessary for an evaluation of fitness function. The function should specify as far as frequently our description gives the optimal and suboptimal graphs. It can be achieved by checking up any range of orders, by calculating for each graph with order N its diameter , and by comparing it with a diameter of optimal graph of the same order.

In a common case the fitness function F evaluates the sum of deviations (quadratic deviations) of diameters from their exact lower bounds for all tested N for circulant graphs having tested analytical descriptions.

In the given version of the program the fitness function works thus: in a cycle we change N in , for each N the diameter of graph is computed, also it is compared with a diameter of optimal graph. If they are equal then graph will be optimum, if they differ on a unit then graph will be suboptimal. The number of all optimum and suboptimal graphs is a value of fitness function and shows quality of the analytical description.

Genetic programming approach has been successfully used for automatic generation of analytical descriptions for families of (sub)optimal circulant networks. The first results have shown that the proposed algorithm finds the description (Theorem 1) for optimal two-dimensional circulants and also the larger part of infinite families of N and their analytical descriptions for double loop circulants obtained in [4], [7] and [1]. Also, the investigations were carried out for three-dimensional circulants: the GPA algorithm has generated previously unknown analytical descriptions of (sub)optimal families of circulants.